package leetcode.pre100;

import java.util.Arrays;

/**
 * 给定一个排序数组，你需要在原地删除重复出现的元素，使得每个元素最多出现两次，返回移除后数组的新长度。
 * <p>
 * 不要使用额外的数组空间，你必须在原地修改输入数组并在使用 O(1) 额外空间的条件下完成。
 * <p>
 * 示例 1:
 * <p>
 * 给定 nums = [1,1,1,2,2,3],
 * <p>
 * 函数应返回新长度 length = 5, 并且原数组的前五个元素被修改为 1, 1, 2, 2, 3 。
 * <p>
 * 你不需要考虑数组中超出新长度后面的元素。
 * 示例 2:
 * <p>
 * 给定 nums = [0,0,1,1,1,1,2,3,3],
 * <p>
 * 函数应返回新长度 length = 7, 并且原数组的前五个元素被修改为 0, 0, 1, 1, 2, 3, 3 。
 * <p>
 * 你不需要考虑数组中超出新长度后面的元素。
 * <p>
 * 相似题目见{@link leetcode.a_总结分布.Code02_数组中缺失或重复数字#deleteDuplicate(int[])}
 *
 * @date 2020/6/8 10:44
 */
public class Code80_RemoveDuplicates_删除数组重复项3 {
    public static void main(String[] args) {
        int[] nums = {1, 1, 1, 2, 2, 3};
    }

    /**
     * 方法1：遍历，遇到重复3个的，把第3个位置让后面所有元素往前移动覆盖
     * 最坏复杂度：O(n²)
     */
    public int removeDuplicates(int[] nums) {
        int i = 1, count = 1, length = nums.length;
        while (i < length) {
            if (nums[i] == nums[i - 1]) {
                count++;
                if (count > 2) {
                    //把i位置元素，从i+1到len-1往前挪
                    remElement(nums, i);
                    //i--,好再次判断i与i+1是否相同
                    i--;
                    //剔除无效位置
                    length--;
                }
            } else {
                count = 1;
            }
            i++;
        }
        return length;
    }

    private int[] remElement(int[] arr, int index) {
        for (int i = index + 1; i < arr.length; i++) {
            arr[i - 1] = arr[i];
        }
        return arr;
    }

    public int removeDuplicates2(int[] nums) {
        if (nums == null) return -1;
        if (nums.length <= 0) return nums.length;
        //j是要被覆盖的元素的位置
        //i是当前遍历的位置
        int j = 1, count = 1;
        for (int i = 1; i < nums.length; i++) {
            //当前元素和上个元素相等
            if (nums[i] == nums[i - 1]) {
                count++;
            } else {
                //不等，则重置count
                count = 1;
            }
            //如果重复数小于2，则把遍历的元素填充到j
            if (count <= 2) {
                nums[j++] = nums[i];
            }
            //TODO   else doNothing,当count > 2，应该淘汰此时的nums[i],所以j不被覆盖，不用做任何事
        }
        return j;
    }

}
